package HighMethod06;

import java.util.*;

/**
 * ClassName:    Sort
 * Package:    HighMethod06
 * Description:
 * Datetime:    2021/4/18 0018   9:25
 * Author: 沈新源
 */
public class QuickSortArray {

    private static void Swap_Ar(int[] arr, int i, int j) {
        int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }


    //函数接入快排
    private static void QuickSort(int[] arr) {
        QuickPass(arr,0,arr.length-1);
    }

    //递归
    private static void QuickPass(int[] arr, int left, int right) {
        if(left < right){
//            int pos = midPartition(arr,left,right);        //三位取中法
//            int pos = partitionSinglePosition(arr,left,right);        //单向划分
            int pos = randomPartition(arr,left,right);        //随机划分
//            int pos = partition(arr,left,right);      //一般划分
            QuickPass(arr,left,pos-1);
            QuickPass(arr,pos+1,right);
        }

    }

    //随机划分：随机交换后再调用partition（）
    public static int randomPartition(int arr[],int left,int right){
        Random random = new Random();
        int index = random.nextInt(right-left+1)+left;    //随机数的随机要+1，且随机数要加上原来的基数left
        int tmp = arr[left];
        arr[left] = arr[index];
        arr[index] = tmp;

        return partition(arr,left,right);
    }

    //一般划分(即双向划分)
    public static int partition(int[] arr, int left, int right) {
        //标准节点
        int tmp = arr[left];
        int i = left;
        int j = right;
        while (i < j) {
            while (i < j && arr[j] > tmp) {
                j--;
            }
            if (i < j) {
                arr[i] = arr[j];
            }
            while (i < j && arr[i] <= tmp) {
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = tmp;       //最后找到tmp的真正位置
        return i;
    }

    //三位取中法划分（还要调用双向划分）
    public static int midPartition(int[] arr, int left, int right){

        int midMax = Integer.MIN_VALUE;
        int midMin = Integer.MAX_VALUE;
        int midIndex = 0;
        int labelA = 0;
        int labelB = 0;
        int len = right-left+1; //划分区间的长度
        for(int i=left;i<len+left;i++){
            if(arr[i] > midMax){
                midMax = arr[i];
                labelA++;
            }
            if(arr[i] < midMin){
                midMin = arr[i];
                labelB++;
            }
            if(labelA == len/2||labelB==len/2){
                midIndex = i;
            break;
            }
        }
        Swap_Ar(arr,left,midIndex);
        return partition(arr, left,right);
    }

    // 单向划分
    public static int partitionSinglePosition(int[] arr, int left, int right) {
        int tmp = arr[left];
        int i = left;
        int j = i + 1;      //保证j前的元素值都比tmp大
        while (j <= right) {
            if (arr[j] <= tmp) {
                i++;
                Swap_Ar(arr, i, j);
            }
            j++;
        }
        Swap_Ar(arr, i, left);

        return i;
    }



    //非递归 快速排序
    public static void quickByWhile(int[] arr, int left, int right) {
        /*借助栈
        Stack<Integer> stack = new Stack();
        stack.push(right);
        stack.push(left);
        while(!stack.isEmpty()){
            int i = stack.pop();
            int j = stack.pop();
            int tmp = partition(arr, i, j);
            if(i < tmp) {
                stack.push(i);
                stack.push(tmp - 1);
            }
            if(tmp < j){
                stack.push(tmp + 1);
                stack.push(j);
            }
        }*/

        //借助队列
        if (left >= right) return;
        Queue<Integer> qu = new LinkedList<>();
        qu.offer(left);
        qu.offer(right);
        while (!qu.isEmpty()) {
            left = qu.poll();
            right = qu.poll();

            int tmp = partition(arr, left, right);

            if (tmp-1  > left) {
                qu.offer(left);
                qu.offer(tmp - 1);
            }
            if (tmp + 1 < right) {
                qu.offer(tmp + 1);
                qu.offer(right);
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {56, 78, 12, 34, 90, 67, 100, 45, 23, 89};

        System.out.println(Arrays.toString(arr));

        QuickSort(arr);       //递归法快排
//        quickWhile(arr);      //非递归快排

        System.out.println(Arrays.toString(arr));
    }

    private static void quickWhile(int[] arr) {
        quickByWhile(arr,0,arr.length-1);
    }


}
